package com.aaaa.scheduler.scheduler.nsga;

import com.aaaa.scheduler.pojo.Chromosome;
import com.aaaa.scheduler.scheduler.genetic.GeneticConfiguration;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class NSGAIII {

    /**
     * 功能描述：DJ算法构造参考点  自适应创建H，将每个目标划分为H份
     * 如果 H < M，Das 和 Dennis 的方法就不会产生中间点
     */
    public static double[][] generateReferencePoints(){
        int M = GeneticConfiguration.objectiveList.size();//目标数
        int H = 1;//目标分成H份

        while(comb(H+ M -1, M -1) <= GeneticConfiguration.POPULATION_SIZE){
            H++;
        }
        H--;
        List<List<Double>> rfPoints = generateReferencePointsByDD(H, M);//DD算法产生的参考点
//        System.out.println(rfPoint);

        if(H < M){//在DD算法基础上运用DJ算法
            int H2 = 0;
            while(comb(H+ M -1, M -1)
                    + comb(H2+ M -1, M -1) <= GeneticConfiguration.POPULATION_SIZE) {
                H2++;
            }
            H2--;

            if(H2 > 0){
                List<List<Double>> rfPoints2 = generateReferencePointsByDD(H2, M);//DD算法产生的参考点
                System.out.println(rfPoints2);
                for (List<Double> doubles : rfPoints2) {
                    for (int i = 0; i < doubles.size(); i++) {
                        double aDouble = doubles.get(i);
                        doubles.set(i, aDouble/2 + 0.5/ M);//DJ算法的精髓
                    }
                }
                rfPoints.addAll(rfPoints2);
            }
        }

        //将参考点list转化为数组形式
        int size = rfPoints.size();
        double[][] rfp = new double[size][M];
        for (int i = 0; i < rfPoints.size(); i++) {
            for(int j = 0; j < M; j++){
                rfp[i][j] = rfPoints.get(i).get(j);
            }
        }
        return rfp;
    }


    /**
     * 功能描述：目标归一化
     *
     */
    public static void normalize(Chromosome[] needChosenPopulation){
        int M = GeneticConfiguration.objectiveList.size();//目标数
        //计算理想点  每个目标的最小值组成一个理想点
        double[] idealPoint = new double[M];
        Arrays.fill(idealPoint,Double.MAX_VALUE);
        for (Chromosome chromosome : needChosenPopulation) {
            for (int i = 0; i < M; i++) {
                if(chromosome.getObjectiveFitnessValueList().get(i) < idealPoint[i]){
                    idealPoint[i] = chromosome.getObjectiveFitnessValueList().get(i);
                }
            }
        }
        //TODO 可以使用Nadir point来计算得到比理想点更好的极值点

        //种群中所有个体进行转换，每个个体的目标值组成一个坐标点，减去理想点
        for (Chromosome chromosome : needChosenPopulation) {
            for (int i = 0; i < M; i++) {
                chromosome.getNormalizeObjectiveValueList().set(i, chromosome.getObjectiveFitnessValueList().get(i)-idealPoint[i]);
            }
        }

        //计算极值点，利用ASF函数求得各个目标轴的极值点。就是从种群中选择一个最靠近目标轴的点
        double[][] extremePoints = new double[M][M];
        for (int i = 0; i < M; i++) {//计算每个目标下的极值点
            double min = Double.MAX_VALUE;
            int minIndex = -1;
            for (int j = 0; j < needChosenPopulation.length; j++) {
                //计算每个染色体除了目标i以外的所有目标的最大值
                double cmax = calculateMaxExcept(needChosenPopulation[j], i);
                if(cmax < min){
                    min = cmax;
                    minIndex = j;
                }
            }
            for (int j = 0; j < M; j++) {//记录下第i个目标的极值点
                extremePoints[i][j] = needChosenPopulation[minIndex].getObjectiveFitnessValueList().get(j);
            }
        }
//        System.out.println(Arrays.asList(extremePoints));

        //计算截距
        double[] intercept = calculateIntercept(extremePoints, needChosenPopulation, idealPoint);

        //所有个体的目标进行归一化处理
        for (Chromosome chromosome : needChosenPopulation) {
            for (int i = 0; i < M; i++) {
                Double aDouble = chromosome.getObjectiveFitnessValueList().get(i);
                chromosome.getNormalizeObjectiveValueList().set(i, (aDouble-idealPoint[i])/(intercept[i]-idealPoint[i]));
            }
        }
    }


    /**
     * 功能描述：联系个体和参考点 & 选择操作
     *
     */
    public static Chromosome[] associateAndNiching(Chromosome[] needChosenPopulation){
        Chromosome[] chosen = new Chromosome[GeneticConfiguration.POPULATION_SIZE];//选择之后的染色体种群

        //生成参考点
        double[][] referencePoints = generateReferencePoints();

        //种群个体目标归一化
        normalize(needChosenPopulation);

        //联系参考点和个体   计算出niche数 和 参考点关联的最后一层rank中的个体的集合
        int lastRank = needChosenPopulation[GeneticConfiguration.POPULATION_SIZE-1].getRank();
        int[] niche = new int[referencePoints.length];
        List<Chromosome>[] inLastRank = new List[referencePoints.length];
        for (Chromosome chromosome : needChosenPopulation) {
            double dMin = Double.MAX_VALUE;
            int indexMin = 0;
            Double[] objective = chromosome.getNormalizeObjectiveValueList().toArray(new Double[chromosome.getNormalizeObjectiveValueList().size()]);
            for (int i = 0; i < referencePoints.length; i++) {
                //计算点到线的距离
                double[] s = referencePoints[i];//方向向量，参考点和原点组成
                double[] M0M = new double[objective.length];//直线外一点和直线上一点组成的向量
                for (int j = 0; j < M0M.length; j++) {
                    M0M[j] = objective[j] - s[j];
                }
                double d = pointToLineLength(M0M, s);
                if(d < dMin){
                    dMin = d;
                    indexMin = i;
                }
            }
            chromosome.setDMin(dMin);
            if(chromosome.getRank() == lastRank){
                if(inLastRank[indexMin] == null){
                    inLastRank[indexMin] = new ArrayList<>();
                }
                inLastRank[indexMin].add(chromosome);
            }else{
                niche[indexMin]++;
            }
        }

        //根据论文中的规则 从最后一层rank中选择出K个染色体
        int i;
        for (i = 0; i < GeneticConfiguration.POPULATION_SIZE; i++) {
            if(needChosenPopulation[i].getRank() == lastRank){
                break;
            }
            chosen[i] = needChosenPopulation[i];
        }
        boolean[] rfPointTravel = new boolean[referencePoints.length];//参考点是否与最后一层rank的染色体有关
        Arrays.fill(rfPointTravel,true);

        while(i < GeneticConfiguration.POPULATION_SIZE){
            //选出一个最小niche数的参考点
            int rfPointIndex = minNiche(niche, rfPointTravel);
            if(inLastRank[rfPointIndex]!=null && !inLastRank[rfPointIndex].isEmpty()){
                int index;
                if(niche[rfPointIndex] == 0){
                    index = choseDMinChromesome(inLastRank[rfPointIndex]);
                }else{
                    index = new Random().nextInt(inLastRank[rfPointIndex].size());
                }
                chosen[i++] = inLastRank[rfPointIndex].get(index);
                inLastRank[rfPointIndex].remove(index);
                niche[rfPointIndex]++;
            }else {
                rfPointTravel[rfPointIndex] = false;
            }
        }
        return chosen;
    }

    /**
     * 功能描述：选择距离这个参考点直线最短的染色体
     *
     */
    private static int choseDMinChromesome(List<Chromosome> chromosomes) {
        double min = chromosomes.get(0).getDMin();
        int minIndex = 0;
        for (int i = 1; i < chromosomes.size(); i++) {
            if(chromosomes.get(i).getDMin() < min){
                min = chromosomes.get(i).getDMin();
                minIndex = i;
            }
        }
        return minIndex;
    }

    /**
     * 功能描述：选出最小niche数的参考点集合，并随机从中选一个
     *
     */
    private static int minNiche(int[] niche, boolean[] rfPointTravel) {
        //找到最小niche数
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < niche.length; i++) {
            if(rfPointTravel[i])
                min = Math.min(min, niche[i]);
        }
        //最小niche数的集合
        List<Integer> niches = new ArrayList<>();
        for (int i = 0; i < niche.length; i++) {
            if(rfPointTravel[i] && niche[i] == min){
                niches.add(i);
            }
        }
        Random random = new Random();
        int index = random.nextInt(niches.size());

        return niches.get(index);
    }

    /**
     * 功能描述：根据两个向量计算 点到直线的距离
     *
     */
    private static double pointToLineLength(double[] a, double[] s) {
        double aMod = mod(a);
        double sMod = mod(s);
        double as = pointMultiply(a, s);
        double cos = as / (aMod * sMod);
        double sin = Math.sqrt(1 - Math.pow(cos, 2));
        return aMod * sMod * sin;
    }

    /**
     * 功能描述：两向量的点乘
     *
     */
    private static double pointMultiply(double[] a, double[] s) {
        double result = 0;
        for (int i = 0; i < a.length; i++) {
            result += a[i]*s[i];
        }
        return result;
    }

    /**
     * 功能描述：求向量的模
     *
     */
    private static double mod(double[] a) {
        double result = 0;
        for (double v : a) {
            result += Math.pow(v,2);
        }
        return Math.sqrt(result);
    }

    /**
     * 功能描述：根据n个点，计算超平面的截距
     * 改进：如果矩阵的秩小于M，那么就不能构成超平面，截距取所有目标的最大值
     */
    private static double[] calculateIntercept(double[][] extremePoints, Chromosome[] needChosenPopulation, double[] idealPoint) {
        int M = extremePoints.length;
        //查看极值点矩阵的秩是否小于M
        double constNum = -arrFunction(extremePoints);//常量 也可以用来判断秩
        if(constNum == 0.0){//行列式的值为0，说明不满秩
            double[] intercept = new double[M];
            Arrays.fill(intercept,Double.MIN_VALUE);
            for (Chromosome chromosome : needChosenPopulation) {
                for (int i = 0; i < M; i++) {
                    if(chromosome.getObjectiveFitnessValueList().get(i) > intercept[i]){
                        intercept[i] = chromosome.getObjectiveFitnessValueList().get(i);
                    }
                }
            }
            return intercept;
        }

        double[][][] cramerDxyz = new double[M][M][M];//克莱姆法则中的所有分子   极值点矩阵作为克莱姆法则的分母
        for (int i = 0; i < cramerDxyz.length; i++) {//初始化所有分子
            for (int j = 0; j < cramerDxyz[0].length; j++) {
                for (int k = 0; k < cramerDxyz[0][0].length; k++) {
                    if(i == k) cramerDxyz[i][j][k] = 1;
                    else cramerDxyz[i][j][k] = extremePoints[j][k];
                }
            }
        }
        double[] xishu = new double[M];//超平面方程的系数 不包括常量
        for (int i = 0; i < xishu.length; i++) {
            xishu[i] = arrFunction(cramerDxyz[i]);
        }

        double[] intercept = new double[M];
        for (int i = 0; i < M; i++) {
            intercept[i] = -constNum/xishu[i];
        }

        for (int j = 0; j < intercept.length; j++) {
            if(intercept[j] < idealPoint[j]){
                double[] intercept1 = new double[M];
                Arrays.fill(intercept1,Double.MIN_VALUE);
                for (Chromosome chromosome : needChosenPopulation) {
                    for (int i = 0; i < M; i++) {
                        if(chromosome.getObjectiveFitnessValueList().get(i) > intercept1[i]){
                            intercept1[i] = chromosome.getObjectiveFitnessValueList().get(i);
                        }
                    }
                }
                return intercept1;
            }
        }
        return intercept;
    }

    /**
     * 功能描述：计算行列式
     *
     */
    private static double arrFunction(double[][] extremePoints){//Guass 消去
        double[][] a = new double[extremePoints.length][extremePoints[0].length];
        for (int i = 0; i < extremePoints.length; i++) {
            System.arraycopy(extremePoints[i],0,a[i],0,extremePoints[i].length);
        }
        double k=0;
        for (int p = 0; p<a[0].length-1; p++) {
            for (int r =p+1; r<a.length; r++) {
                if(a[p][p] == 0.0){//交换这两行
                    for (int i = 0; i < a[0].length; i++) {
                        double t = a[p][i];
                        a[p][i] = a[r][i];
                        a[r][i] = t;
                    }
                }else{
                    k=a[r][p]/a[p][p];
                    a[r][p]=0;
                    for (int c = p+1; c<a[0].length; c++) {
                        a[r][c]=a[r][c]-k*a[p][c];
                    }//u
                }
            }//r
        }//c
        double result = 1.0;
        for (int i = 0; i<a.length; i++) {//计算主对角线相乘的结果
            result=result*a[i][i];
        }//i
        return result;
    }

    /**
     * 功能描述：计算染色体中除了第i个目标 其他所有目标中的最大值
     *
     */
    private static double calculateMaxExcept(Chromosome chromosome, int i) {
        double max = Double.MIN_VALUE;
        for (int j = 0; j < chromosome.getObjectiveFitnessValueList().size(); j++) {
            if(j == i){
                continue;
            }else{
                double iOb = chromosome.getNormalizeObjectiveValueList().get(j);
                if(iOb > max){
                    max = iOb;
                }
            }
        }
        return max;
    }


    /**
     * 功能描述：DD算法构造参考点
     *
     */
    private static List<List<Double>> generateReferencePointsByDD(int H, int M) {
        List<List<Double>> com = new ArrayList<>();
        combinations(com, new ArrayList<>(),H+M-1,M-1, 0);

        List<List<Double>> W = new ArrayList<>(com);
        for (List<Double> doubles : W) {//最后增加一列 值全是H的列
            doubles.add((double) H);
        }

        for (List<Double> doubles : W) {
            for (int j = W.get(0).size() - 1; j > 0; j--) {//目标为3的参考点计算：[[a-0],[b-a],[1-b]]
                doubles.set(j, (doubles.get(j) - doubles.get(j - 1)) / H);
            }
            doubles.set(0, doubles.get(0) / H);
        }

        return W;
    }

    /**
     * 功能描述：收集0-n内，长度为k的组合数的实例。 所有组合数都做一个减法处理：减一个向量[0,1,...,k]
     *
     */
    private static void combinations(List<List<Double>> result, List<Double> list, int n, int k, int start) {
        if(list.size() == k){
            ArrayList<Double> Doubles = new ArrayList<>(list);
            for (int i = 0; i < Doubles.size(); i++) {
                Doubles.set(i, Doubles.get(i) - i);
            }
            result.add(Doubles);
            return ;
        }
        for(int i=start; i<n; i++){
            list.add((double) i);
            combinations(result, list, n, k, i+1);
            list.remove(list.size()-1);
        }
    }

    /**
     * 功能描述：计算Cnk，组合数
     *
     */
    private static long comb(int n, int k){
        k = Math.min(k, n-k);
        long nk = 1, kk = 1;
        for(int i=n,j=0; i>=1&&j<k; i--,j++){
            nk *= i;
        }
        for(int i=k; i>=1; i--){
            kk *= i;
        }
        return (long) ((double)(nk/kk));
    }


    public static void main(String[] args) {

        Chromosome chromosome = new Chromosome(new Random());
        List<Double> objective = new ArrayList<>();
        objective.add(0.1);
        objective.add(0.2);
        objective.add(0.3);
        chromosome.setObjectiveFitnessValueList(objective);
        Double[] objectives = chromosome.getObjectiveFitnessValueList().toArray(new Double[chromosome.getObjectiveFitnessValueList().size()]);
        for (Double aDouble : objectives) {
            System.out.println(aDouble);
        }

    }
}
